package com.lwg.datastructure.commonSortingAlgorithm;

import java.util.Arrays;

/**
 * @author: lwg
 * @Date: 2022/4/22 15:40
 * @Description: 快速排序
 * 选择一个基点，将小于改基点的数放在该数前面，剩下的就是大于该数的数了
 * 步骤：定义两个位置的指针，分别指向最左边和最右边
 * 最右边的一直找到比基准数(此以最左边的数为基准数)小的数字，再停止，
 * 最左边的一直找到比基准数大的数字，再停止，然后交换两个数字
 * 当两个指针位置相等的时候，将此位置的数字与基准数交换
 * <p>
 * 疑问：为什么要先从最右侧开始走？
 * 因为从最右侧开始走 可以保证当两个指针相遇的时候所指向的数小于或等于基准数，
 * 第一次遍历数字与基准数相等的时候，即便和基准数相等的数字没有交换，但是后面循环的时候也会调换
 */
public class QuickSort {
    
    public static void main(String[] args) {
        int[] arr = {101, 119,101, 34, 119, 1, -1, 90,-1,-1,119, 123, 101};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        //首先保证左指针不能超过右指针，否则将会错乱
        if (left > right) {
            return;
        }
        // 保存定义的基准数
        int base = arr[left];
        // 定义左指针和右指针指向的位置
        int i = left;
        int j = right;
        
        // 1.当左指针和右指针不相等的时候，只判断指针是否继续移动
        while (i != j) {
            // 当右指针指向的位置的数小于基准数时停止移动，即跳出循环
            // 即右指针指向的位置的数大于等于基准数时，移动右指针
            while (arr[j] >= base && j > i) {
                j--;
            }
            
            // 当左指针指向的位置的数大于基准数时停止移动，即跳出循环
            // 当左指针指向的位置的数小于等于基准数时，移动左指针
            while (arr[i] <= base && j > i) {
                i++;
            }
            
            // 都停止后交换两个指针指向的位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        
        // 2.当两个指针相遇后 交换当前指针指向的数和基准数
        arr[left] = arr[i];
        arr[i] = base;
        quickSort(arr, 0, i - 1);
        quickSort(arr, i + 1, right);
    }
}
